/*
https://leetcode-cn.com/problems/shopping-offers/solution/da-li-bao-by-leetcode-solution-p1ww/
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution638 {
    Map<List<Integer>,Integer> map=new HashMap<>();

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        List<List<Integer>> list=new ArrayList<>();
        for (List<Integer> integers : special) {
            int t=0,p=0;
            for (int i=0;i<price.size();i++){
                t=t+price.get(i)*integers.get(i);
                p=p+integers.get(i);
            }
            if (p!=0 && t>integers.get(price.size())){
                list.add(integers);
            }
        }
        return search(price,needs,list);
    }
    public int search(List<Integer> price,List<Integer> needs,List<List<Integer>> lists){
        if (!map.containsKey(needs)){
            int min=0;
            for (int i=0;i<price.size();i++){
                min=min+price.get(i)*needs.get(i);
            }
            for (List<Integer> list : lists) {
                int specialPrice=list.get(price.size());
                List<Integer> nextNeeds=new ArrayList<>();
                for (int i=0;i<price.size();i++){
                    if (list.get(i)>needs.get(i)){
                        break;
                    }
                    nextNeeds.add(needs.get(i)-list.get(i));
                }
                if (nextNeeds.size()==price.size()){
                    min=Math.min(min,search(price,nextNeeds,lists)+specialPrice);
                }
            }
            map.put(needs,min);
        }
        return map.get(needs);
    }

    public static void main(String[] args) {
        List<Integer> price=new ArrayList<>();
        price.add(2);
        price.add(5);
        List<Integer> l1=new ArrayList<>();
        l1.add(3);
        l1.add(0);
        l1.add(5);
        List<Integer> l2=new ArrayList<>();
        l2.add(1);
        l2.add(2);
        l2.add(10);
        List<List<Integer>> special=new ArrayList<>();
        special.add(l1);
        special.add(l2);
        List<Integer> needs=new ArrayList<>();
        needs.add(3);
        needs.add(2);
        System.out.println(new Solution638().shoppingOffers(price,special,needs));
    }
}
